<?php
/**
 *  User：LRZ
 *  Date：2020/2/11
 *  Time：15:33
 */

/**
 *  202.快乐数
 *
 *  标签：哈希值、数学
 *
 *  编写一个算法来判断一个数是不是“快乐数”。
 *  一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。
 *
 *  示例: 
 *      输入: 19
 *      输出: true
 *      解释:
 *          1^2 + 9^2 = 82
 *          8^2 + 2^2 = 68
 *          6^2 + 8^2 = 100
 *          1^2 + 0^2 + 0^2 = 1
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/happy-number
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$n   = 19;
$res = isHappy($n);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function isHappy($n)
{
    $slow = $n;
    $fast = $n;
    do {
        $slow = bitSquareSum($slow);
        $fast = bitSquareSum($fast);
        $fast = bitSquareSum($fast);
    } while ($slow !== $fast);

    return $slow === 1;
}

function bitSquareSum($n)
{
    $sum = 0;
    while ($n > 0) {
        $bit = $n % 10;
        $sum += $bit * $bit;
        $n   = (int)($n / 10);
    }
    return $sum;
}